#include <iostream>
#include <queue>
#include <string>
#include <functional>
#include <map>
using namespace std;

namespace YX
{
    template<typename W>
    struct HFMTreeNode
    {
        struct HFMTreeNode<W>* _parent;
        struct HFMTreeNode<W>* _left;
        struct HFMTreeNode<W>* _right;
        pair<char,W> _cw;

        HFMTreeNode(const pair<char,W>& cw)
            :_parent(nullptr)
            ,_left(nullptr)
            ,_right(nullptr)
            ,_cw(cw)
        {

        }
       
        // 运算符重载---用于仿函数进行比较
        bool operator>(const HFMTreeNode<W>& n)
        {
            return _cw.second>n._cw.second;
        }

    };

    template<class T>
    struct greater 
    {
        bool operator()(const T& x,const T& y)
        {
            return *x>*y;
        }
    };

    template<class W>
    class HFMTree 
    {
        typedef HFMTreeNode<W> Node;
        private:
            Node* _root; // 根结点
            vector<pair<Node*,string>> _leaves; // 记录叶子结点
        public:

            // 用一串字符构建哈夫曼树
            HFMTree(const string& str)
                :_root(nullptr)
            {
                // 统计字符出现的个数
                map<char,int> m; 
                for(const auto& e:str)
                {
                    m[e]++;
                }
                
                // 将对应的字符及其出现的次数压入优先级队列中
                priority_queue<Node*,vector<Node*>,YX::greater<Node*>> pq; 

                map<char,int>::iterator it=m.begin();
                while(it!=m.end())
                {
                    Node* newNode=new Node(make_pair(it->first,it->second));
                    pq.push(newNode);

                    // 记录叶子结点
                    _leaves.push_back(make_pair(newNode,string()));

                    it++;
                }
                
                // 选出最小权值与次小权值的结点进行链接
                while(pq.size()!=1)
                {
                    Node* left=pq.top();
                    pq.pop();
                    Node* right=pq.top();
                    pq.pop();
                   
                    // parent的权值为两结点的权值之和
                    Node* parent=new Node(make_pair(char(),left->_cw.second+right->_cw.second));

                    parent->_left=left;
                    left->_parent=parent;

                    parent->_right=right;
                    right->_parent=parent;

                    // 链接完成之后将parent结点压入堆中
                    pq.push(parent);
                }

                // 优先级队列中最后一个结点即为根结点
                _root=pq.top();
            }

            // 生成哈夫曼编码
            void HFM_Coding()
            {
                for(size_t i=0;i<_leaves.size();i++)
                {
                    Node* curr=_leaves[i].first;
                    
                    while(curr->_parent!=nullptr)
                    {
                        if(curr->_parent->_left==curr)
                        {
                            _leaves[i].second.insert(0,1,'0');
                        }
                        else if(curr->_parent->_right==curr)
                        {
                            _leaves[i].second.insert(0,1,'1');
                        }
                        curr=curr->_parent;
                    }

                }
                
                for(const auto& e:_leaves)
                {
                    cout<<(e.first)->_cw.first<<":"<<e.second<<endl;
                }

            }

            // 用n个权值来构造哈夫曼树
            //HFMTree(const W* a,size_t n)
            //    :_root(nullptr)
            //{

            //    priority_queue<Node*,vector<Node*>,YX::greater<Node*>> pq;
            //    
            //    for(size_t i=0;i<n;i++)
            //    {
            //        Node* newNode=new Node(a[i]);

            //        // 先将叶子结点push到优先级队列中
            //        pq.push(newNode);
            //        // 记录叶子结点---默认编码为int最大值
            //        _leaves.push_back(make_pair<newNode,INT32_MAX>);
            //    }
            //    
            //    while(pq.size()!=1)
            //    {
            //        // 将最小权值和次小权值结点出堆
            //        Node* left=pq.top();
            //        pq.pop();
            //        Node* right=pq.top();
            //        pq.pop();

            //        // 生成新结点（权值为最小权值和次小权值的和）将出堆的两个结点链成其左右孩子
            //        Node* parent = new Node(left->_w+right->_w);

            //        parent->_left=left;
            //        left->_parent=parent;

            //        parent->_right=right;
            //        right->_parent=parent;

            //        pq.push(parent);
            //    }

            //    _root=pq.top();

            //}

        void _prev_order(Node* root)
        {
            if(root==nullptr)
            {
                return;
            }

            cout<<root->_cw.second<<endl;
            _prev_order(root->_left);
            _prev_order(root->_right);
        }   

        void prev_order()
        {
            _prev_order(_root);
        }
    };


};
//
//namespace YX
//{
//    template<typename W>
//    struct HFMTreeNode
//    {
//        struct HFMTreeNode<W>* _parent;
//        struct HFMTreeNode<W>* _left;
//        struct HFMTreeNode<W>* _right;
//        W _w;
//
//        HFMTreeNode(const W& w)
//            :_parent(nullptr)
//            ,_left(nullptr)
//            ,_right(nullptr)
//            ,_w(w)
//        {
//
//        }
//       
//        // 运算符重载---用于仿函数进行比较
//        bool operator>(const HFMTreeNode<W>& n)
//        {
//            return _w>n._w;
//        }
//
//    };
//
//    template<class T>
//    struct greater 
//    {
//        bool operator()(const T& x,const T& y)
//        {
//            return *x>*y;
//        }
//    };
//
//    template<class W>
//    class HFMTree 
//    {
//        typedef HFMTreeNode<W> Node;
//        private:
//            Node* _root; // 根结点
//            vector<pair<Node*,int>> _leaves; // 记录叶子结点
//        public:
//
//            // 用n个权值来构造哈夫曼树
//            HFMTree(const W* a,size_t n)
//                :_root(nullptr)
//            {
//
//                priority_queue<Node*,vector<Node*>,YX::greater<Node*>> pq;
//                
//                for(size_t i=0;i<n;i++)
//                {
//                    Node* newNode=new Node(a[i]);
//
//                    // 先将叶子结点push到优先级队列中
//                    pq.push(newNode);
//                    // 记录叶子结点---默认编码为int最大值
//                    _leaves.push_back(make_pair<newNode,INT32_MAX>);
//                }
//                
//                while(pq.size()!=1)
//                {
//                    // 将最小权值和次小权值结点出堆
//                    Node* left=pq.top();
//                    pq.pop();
//                    Node* right=pq.top();
//                    pq.pop();
//
//                    // 生成新结点（权值为最小权值和次小权值的和）将出堆的两个结点链成其左右孩子
//                    Node* parent = new Node(left->_w+right->_w);
//
//                    parent->_left=left;
//                    left->_parent=parent;
//
//                    parent->_right=right;
//                    right->_parent=parent;
//
//                    pq.push(parent);
//                }
//
//                _root=pq.top();
//
//            }
//
//        void _prev_order(Node* root)
//        {
//            if(root==nullptr)
//            {
//                return;
//            }
//
//            cout<<root->_w<<endl;
//            _prev_order(root->_left);
//            _prev_order(root->_right);
//        }   
//
//        void prev_order()
//        {
//            _prev_order(_root);
//        }
//    };
//
//
//};
